//
// Created by Administrator on 2021/4/13.
//

/*给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：3

示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

提示：
树的深度不会超过 1000 。
树的节点数目位于 [0, 104] 之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <utility>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val = 0;
    vector<Node *> children;

    Node() = default;

    explicit Node(int _val) : val(_val) {};

    Node(int _val, vector<Node *> _children) {
        val = _val;
        children = std::move(_children);
    }
};

class Solution {
public:
    int maxDepth(Node *root) {
        // 层序遍历
        if (!root) return 0;
        queue<Node *> q;
        q.push(root);
        int depth = 0;
        while (!q.empty()) {
            int currentLevelSize = (int) q.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front();
                q.pop();
                for (auto &x:node->children) {
                    q.push(x);
                }
            }
            depth++;
        }
        return depth;
    }
};

class Solution2 {
public:
    int maxDepth(Node *root) {
        return dfs(root,0);
    }

    int dfs(Node *root, int depth) {
        if (!root) return 0;
        int maxDepth = 0;
        for (auto &x:root->children) {
            maxDepth = max(maxDepth, dfs(x, depth));
        }
        return maxDepth + 1;
    }

};

int main() {
    auto t6 = Node(6);
    auto t5 = Node(5);
    auto t4 = Node(4);
    auto t3 = Node(2);
    auto t2 = Node(3, vector<Node *>{&t5, &t6});
    auto t1 = Node(1, vector<Node *>{&t2, &t3, &t4});
    Solution2 sol;
    cout << sol.maxDepth(&t1);
    return 0;
}